#pragma once

enum Color
{
	Red,
	Black
};

template<class T>
struct RBTreeNode
{
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	T _data;
	Color _col;

	

	RBTreeNode(const T& data)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_data(data)
		,_col(Red)
	{}

};


template<class T>
struct TreeIterator
{
	typedef RBTreeNode<T> Node;
	typedef TreeIterator<T> self;



	TreeIterator(Node* node)
		:_node(node)
	{}

	T& operator*()
	{
		return _node->_data;
	}

	T* operator->()
	{
		return &_node->_data;
	}

	bool operator!=(const self& s)
	{
		return _node != s._node;
	}
	self operator++()
	{

		if (_node->_right)
		{
			_node = MOstLeft(_node);
		}
		else
		{
			Node* cur = _node;
			Node* parent = _node->_parent;
			while (parent)
			{
				if (cur = parent->_left)
				{
					break;
				}
				else
				{
					cur = parent;
					parent = parent->_parent;
				}
			}
			_node = parent;
		}

		return *this;
	}

	Node* MOstLeft(Node* cur)
	{
		while (cur->_left)
		{
			cur = cur->_left;
		}

		return cur;
	}

	Node* _node;
};

template<class K, class T>
class RBTree
{
	typedef RBTreeNode<T> Node;
public:


	


	RBTree()
		:_root(nullptr)
	{}

	bool find(const K& key)
	{

	}

	bool insert(const T& data)
	{

	}

private:
	Node* _root;
};